package snippet;
import java.util.*;
public class 电话号码的字母组合 {
	List<String> result = new ArrayList<>();
	Map<String,String> map = new HashMap<>();
	StringBuilder stb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
    	map.put("2", "abc");
    	map.put("3", "def");
    	map.put("4", "ghi");
    	map.put("5", "jkl");
    	map.put("6", "mno");
    	map.put("7", "pqrs");
    	map.put("8", "tuv");
    	map.put("9", "wxyz");

    	backtracking(digits, 0);
    	System.out.println(result.size());
    	System.out.println(result);
    	return result;
    }
    public void backtracking(String digits, int index) {
    	if(stb.length() == digits.length()) {
    		if(!stb.toString().isEmpty()) {
    			result.add(stb.toString());
    		}
    		return;
    	}
    	
    	for(int i = index; i < digits.length(); i++) {
    		String str = map.get(String.valueOf(digits.charAt(i)));
    		for(int j = 0; j < str.length(); j++) {
    			stb.append(String.valueOf(str.charAt(j)));
    			backtracking(digits, i + 1);
    			stb.deleteCharAt(stb.length() - 1);
    		}
    	}
    }
    
    public static void main(String[] args) {
		new 电话号码的字母组合().letterCombinations("");
	}
}
